#ifndef QUADTREE_H_
#define QUADTREE_H_

#include <assert.h>
#include <list>

#include "fish.h"
#include "FishThread.h"

class LeafNode;
class TreeNode;
class FishThread;

typedef std::list < fish_t * >FishList;

/*
 * NOTE: the following ordering must be true:
 * right > left
 * bottom > top
 */

class QuadTree
{
public:
    QuadTree( TreeNode * parent, int whichChild, int owner, double left,
              double right, double top, double bottom )
            : parent( parent ), whichChild( whichChild ), owner( owner ), left( left ),
            right( right ), top( top ), bottom( bottom ) {
        assert( right > left );
        assert( bottom > top );
    } virtual ~ QuadTree() {
    }

    virtual void insert( fish_t * fish ) = 0;
    virtual void splitUp( FishThread & ) = 0;
    virtual void cleanupRoots( FishThread & ) = 0;
    virtual void stealFish( FishList &, FishThread & ) = 0;
    //NB: make sure to updateFishCount() before calling collapse
    virtual void collapse( FishThread & ) = 0;
    virtual int updateFishCount() = 0;

    virtual void distributeFish( int &currentThread, int &fishOwned,
                                 FishThread threads[] ) = 0;

    virtual void interact( fish_t & f, const LeafNode * const originator ) =
        0;
    virtual bool findHome( fish_t & fish, LeafNode * &newNode,
                           int &newThread ) = 0;

    static int NumThreads;
    static int NumFish;
    /*
     * if a leafnode contains > MaxFish, it will be replaced with a treenode
     * and the fish will be divided up
     */
    static int MaxFish;
    /*
     * if a treenode (and its children) contain < MinFish it will be replaced
     * by a leafnode
     */
    static int MinFish;
    static QuadTree *Root;


    //the 4 sides of this quad
    double left, right, top, bottom;
    TreeNode *parent;
    //which thread owns me
    int owner;
    //which of my parent's 4 children am I?
    int whichChild;
    int nFishOwned;
};

class LeafNode: public QuadTree
{
public:
    LeafNode( TreeNode * parent, int whichChild, int owner, double left,
              double right, double top, double bottom )
            : QuadTree( parent, whichChild, owner, left, right, top, bottom ) {
    } virtual ~ LeafNode() {
    }

    virtual void insert( fish_t * fish );
    virtual void splitUp( FishThread & );
    virtual void cleanupRoots( FishThread & ) {
    }
    virtual void stealFish( FishList &, FishThread & );
    virtual void collapse( FishThread & ) {
    }
    virtual int updateFishCount();
    virtual void distributeFish( int &currentThread, int &fishOwned,
                                 FishThread threads[] );
    virtual void interact( fish_t & f, const LeafNode * const originator );
    /*
     * perform all pair-wise interactions of fish in this quad
     * updating all the fish in this quad
     */
    virtual void intraQuadInteract();
    /*
     * update the accelerations of only the fish in this quad,
     * computing the interactions with fish in other quads
     */
    virtual void interQuadInteract();

    virtual bool findHome( fish_t & fish, LeafNode * &newNode,
                           int &newThread );
    virtual bool belongsHere( fish_t & fish );

    FishList contents;
};


class TreeNode: public QuadTree
{
public:
    TreeNode( TreeNode * parent, int whichChild, int owner, double left,
              double right, double top, double bottom );

    virtual ~ TreeNode();

    virtual void insert( fish_t * fish );
    virtual void splitUp( FishThread & );
    /*
     * remove myself from the thread's root list if my parent is also owned
     * and therefore will also appear in the root list
     */
    virtual void cleanupRoots( FishThread & );
    virtual void stealFish( FishList &, FishThread & );
    virtual void collapse( FishThread & );
    virtual int updateFishCount();
    virtual void distributeFish( int &currentThread, int &fishOwned,
                                 FishThread threads[] );
    virtual void interact( fish_t & f, const LeafNode * const originator );
    virtual bool findHome( fish_t & fish, LeafNode * &newNode,
                           int &newThread );

    //how many children are under me & my children
    int numChildren;
    //the 4 quads are numbered clockwise, upper left is 0
    /* it looks like this, the arrow indicates increasing coordinates
     *  |------>
     *  |  0 1
     *  |  2 3
     * \|/
     *
     */
    QuadTree *children[4];
    //if less than verticalCenter, then in quads 0 or 1
    //if less than horizCenter, then in quads 0 or 2
    double verticalCenter, horizCenter;
};



#endif                          /*QUADTREE_H_ */
